package cn.zifangsky.dp.questions;

import org.junit.Test;

/**
 * 换钱的最少货币数
 *
 * <p>【题目】</p>
 * <p>给定数组 arr，arr 中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim，代表要找的钱数，求组成aim的最少货币数。</p>
 * <p>【举例】</p>
 * <p>arr={5, 2, 3}, aim=20</p>
 * <p>4张5元可以组成20元，其他的找钱方案都要使用更多张的货币，所以返回4。</p>
 *
 * @author zifangsky
 * @date 2020/5/27
 * @since 1.0.0
 */
public class Problem_006_MinCoins {

    /**
     * 测试代码
     */
    @Test
    public void testMethods(){
        int[] arr = {5, 2, 3};
        int aim = 20;
//        int[] arr = {3, 6, 7};
//        int aim = 20;

        //1. 测试方法一
        System.out.println(solution1(arr, aim));
        //2. 测试方法二
//        System.out.println(solution2(arr, aim));
    }


    /**
     * 解法一：使用暴力递归方式求解
     *
     * @param arr 数组
     * @param aim 目标金额
     */
    private int solution1(int[] arr, int aim){
        if(arr == null || arr.length < 1 || aim < 0){
            return 0;
        }

        return process(arr, 0, aim);
    }

    /**
     * 递归处理
     * @param arr 不同货币值组成的数组
     * @param index 当前的数组索引
     * @param rest 剩余金额
     */
    private int process(int[] arr, int index, int rest){
        //1. 如果剩余金额为0直接返回
        if(rest == 0){
            return 0;
        }

        //2. 如果当前 index 已经超过数组最大长度，则返回 -1，表示当前没有方案
        if(index == arr.length){
            return -1;
        }

        int result = -1;
        //3. 序列为index的货币值使用 i 张，但是金额不能超过rest
        for(int i = 0; (arr[index]*i) <= rest; i++){
            //4. 剩余金额交给的后面货币值去拼装
            int nextRest = process(arr, (index + 1), (rest- arr[index]*i));

            //如果结果有效
            if(nextRest != -1){
                //5. 计算当前方案的总数
                int curNum = i + nextRest;
                //6. 除了第一种方案，其他方案需要跟前一种方案对比使用的货币总数，最后保存使用货币总数较少那种方案
                result = (result == -1) ? curNum : Math.min(result, curNum);
            }
        }

        //7. 返回最终结果
        return result;
    }


}
